package hot100;

/**
 * @Author: wzp
 * @CreateTime: 2024-09-11  13:04
 * @Description:
 * @Version: 1.0
 */
public class hot_0000 {
    public static int minDistance=Integer.MAX_VALUE;
    public int minDistance(String word1, String word2) {
        char[] chars1=word1.toCharArray();
        char[] chars2=word2.toCharArray();
        dfs(chars1,chars2,chars1.length-1,chars2.length-1,0);
        return minDistance;
    }
    public void dfs(char[] word1,char[] word2,int i,int j,int count){
        if(i==-1&&j!=-1){
            count+=j+1;
            if(count<minDistance){
                minDistance=count;
            }
            return;
        }
        if(j==-1&&i!=-1){
            count+=i+1;
            if(count<minDistance){
                minDistance=count;
            }
            return;
        }
        if(i==-1&&j==-1){
            if(count<minDistance){
                minDistance=count;
            }
            return;
        }
        if(word1[i]==word2[j]){
            dfs(word1,word2,i-1,j-1,count);
        }else{
//            插
            dfs(word1,word2,i,j-1,count+1);
//            删
            dfs(word1,word2,i-1,j,count+1);
//            改
            dfs(word1,word2,i-1,j-1,count+1);
        }


    }

}
